Graph / Feedback vertex set (Bibtex)

P432: Enumeration of all minimal feedback vertex sets in a graph

Input:

A graph $G$.

Output:

All minimal feedback vertex sets in $G$.

Complexity:

Comment:

Reference:

[Yau1967] (Bibtex)

P177: Enumeration of all feedback vertex sets in a strongly connected directed graph

Input:

A strongly connected directed graph $G = (V, E)$ and an integer $k$.

Output:

All feedback vertex sets of size $k$ in $G$.

Complexity:

$O(|V|^{k-1}|E|)$ total time and $O(|E|)$ space.

Comment:

Reference:

[Garey1978] (Bibtex)

P22: Enumeration of all minimal feedback vertex sets in a graph

Input:

A graph $G=(V,E)$.

Output:

All minimal feedback vertex sets in $G$.

Complexity:

$O(|V||E|(|V|+|E|))$ time delay.

Comment:

Theorem 2

Reference:

[Schwikowski2002] (Bibtex)

P23: Enumeration of all minimal feedback vertex sets in a directed graph

Input:

A directed graph $G=(V,E)$.

Output:

All minimal feedback vertex sets in $G$.

Complexity:

$O(|V|^2(|V|+|E|))$ time delay.

Comment:

Theorem 1

Reference:

[Schwikowski2002] (Bibtex)